#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> dp[2000];
        dp[0].push_back("");
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                int k = i - j - 1;
                for (int ii = 0; ii < dp[j].size(); ii++)
                {
                    for (int jj = 0; jj < dp[k].size(); jj++)
                    {
                        string str = "(" + dp[j][ii] + ")" + dp[k][jj];
                        dp[i].push_back(str);
                    }
                }
            }
        }
        return dp[n];
    }
};
int main()
{
    Solution sol;
}